/**
 * Created by L.jp
 * Description:一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
 * User: 86189
 * Date: 2021-12-18
 * Time: 17:38
 */
//数据范围：0 \leq n \leq 400≤n≤40
        //要求：时间复杂度：O(n) ，空间复杂度： O(1)
    //示例3
//输入：
//0
//返回值：
//0

public class Solution {
    public static int jumpFloor(int target) {
        //dp算法
        //状态定义：dp[i]：跳到第i层台阶的跳法
        //状态转移方程：经过递推发现，dp[i]=dp[i-1]+dp[i-2]
        //初始化：dp[0]=1,其实有点奇怪，但是如果没有这个第0个台阶的跳法的话就算不出来后面台阶的跳法
        //dp[1]=1;
        /*

        int[] dp=new int[target+1];
        dp[0]=1;
        dp[1]=1;
        for(int i=2;i<=target;i++){
            dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[target];

         */

        //经过分析发现i的状态只跟前一项和前两项有关，所以可以优化，不断更新第一项和第二项的值
        //实际就是斐波那契的算法
        int f1=1;//一个台阶的跳法
        int f2=2;//两个台阶的跳法
        int f3=target;
        while(target>2){//需要计算的次数
            f3=f1+f2;
            f1=f2;
            f2=f3;
            target--;
        }
        return f3;
    }
    public static void main(String[] args) {
        System.out.println(jumpFloor(4));
    }
}
